package algorithm.t202110;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/17 9:31
 * @description :7道 She said where'd you wanna go,how much you wanna risk?
 *                          No human is limited,Eliud Kipchoge
 *                          persevere to last 2021.10.17 LiHongLei
 */
public class t20211017 {


    //733.图像渲染
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image == null || sr > image.length - 1 || sc > image[0].length || sr < 0 || sc < 0 || image[sr][sc] == newColor) {
            return image;
        }

        int olrColor = image[sr][sc];//拿到规定颜色。我们要做的是把颜色是oldColor的像素渲染成newColor

        return print(image, sr, sc, olrColor, newColor);

    }

    public int[][] print(int[][] image, int sr, int sc, int oldColor, int newColor) {

        if (image == null || sc < 0 || sr < 0 || sr > image.length - 1 || sc > image[0].length - 1 || image[sr][sc] == newColor) {
            return image;
        }
        if (image[sr][sc] != oldColor) {
            return null;
        }
        image[sr][sc] = newColor;
        print(image, sr - 1, sc, oldColor, newColor);
        print(image, sr + 1, sc, oldColor, newColor);
        print(image, sr, sc - 1, oldColor, newColor);
        print(image, sr, sc + 1, oldColor, newColor);

        return image;

    }


    //695.岛屿的最大面积
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null) {
            return -1;

        }

        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 0) {
                    int num = dfs(grid, i, j);
                    max = Math.max(max, num);
                }

            }
        }

        return max;
    }

    public int dfs(int[][] matrix, int x, int y) {

        if (matrix == null || x < 0 || y < 0 || x > matrix.length - 1 || y > matrix[0].length - 1) {
            return 0;
        }

        if (matrix[x][y] == 0) {
            return 0;
        } else {
            matrix[x][y] = 0;
            return 1 + dfs(matrix, x - 1, y) +
                    dfs(matrix, x + 1, y) +
                    dfs(matrix, x, y - 1) +
                    dfs(matrix, x, y + 1);
        }


    }


    public static void main(String[] args) {
        t20211017 t20211017 = new t20211017();


        int[][] arr = new int[2][3];
        arr[0][0] = 0;
        arr[0][1] = 0;
        arr[0][2] = 0;

        arr[1][0] = 1;
        arr[1][1] = 1;
        arr[1][2] = 0;

        SortedStack sortedStack = new SortedStack();
        sortedStack.push(11);
        sortedStack.push(8);
        sortedStack.push(7);
        sortedStack.push(31);
        sortedStack.push(22);

        sortedStack.pop();
        System.out.println(sortedStack.peek());


    }

}

class StackDiv {

    int[] arr;
    int near = -1;

    ArrayList<Integer> list = new ArrayList<>();


    public StackDiv(int capacity) {
        arr = new int[capacity];
    }


    public boolean isFull() {
        return near == arr.length - 1;
    }

    public boolean isEmpty() {
        return near == -1;
    }


    public void push(int element) {
        if (isFull()) {
            System.out.println("栈已经满了，无法继续添加元素");
            return;
        }
        list.add(element);

        arr[++near] = element;

    }

    public int geMin() {
        if (isEmpty()) {
            System.out.println("栈为空，无法获取最小元素");
            return -1;
        }
        Collections.sort(list);
        return list.get(0);

    }

    public void pop() {
        if (isEmpty()) {
            System.out.println("栈为空，无法弹出元素7");
            return;
        }

        near--;

    }

    //得到栈顶元素，不会影响栈的数据结构
    public int top() {
        if (isEmpty()) {
            System.out.println("栈为空，无法得到栈顶元素");
            return -1;
        }
        return arr[near];

    }

}

//面试题03.02 栈的最小值
class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;//存放最小数的栈，其由下往上为递增，意思就是该栈顶永远为最小元素


    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || minStack.peek() >= x) {
            minStack.push(x);
        }
    }

    public void pop() {
        int res = stack.pop();
        if (minStack.peek() >= res) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }


}

//面试题03.01 三合一
class TripleInOne2 {

    int[] arr;

    //若stackSiz为3
    int near1 = -1;
    int near2 = -1;// + arr.length;//2
    int near3 = 10;//near2 + arr.length;//5


    public TripleInOne2(int stackSize) {
        System.out.println("构造方法不执行？？？");
        arr = new int[stackSize];
    }


    public void push(int stackNum, int value) {
        //先判断是否栈满
        if (stackNum == 1) {
            if (near1 == arr.length - 1) {
                System.out.println("栈满，无法压栈");
                return;
            } else {
                arr[++near1] = value;
            }
        } else if (stackNum == 2) {
            if (near2 == -1 + arr.length + arr.length) {
                System.out.println("栈满，无法压栈");
                return;
            } else {
                arr[++near2] = value;
            }
        } else {
            if (near3 == near2 + arr.length + arr.length) {
                System.out.println("栈满，无法压栈");
                return;
            } else {
                arr[++near3] = value;
            }
        }


    }

    public int pop(int stackNum) {
        //先判断栈是否为空
        if (stackNum == 1) {
            if (near1 == -1) {
                System.out.println("栈为空");
                return -1;
            } else {
                int res = arr[near1--];
                return res;
            }
        } else if (stackNum == 2) {
            if (near2 == -1 + arr.length) {
                System.out.println("栈为空");
                return -1;
            } else {
                int res = arr[near2--];
                return res;
            }
        } else {
            if (near3 == near2 + arr.length) {
                System.out.println("栈为空");
                return -1;
            } else {
                int res = arr[near3--];
                return res;
            }
        }
    }


    public int peek(int stackNum) {
        //先判断栈是否为空
        if (stackNum == 1) {
            if (isEmpty(stackNum)) {
                System.out.println("栈为空");
                return -1;
            } else {
                return arr[near1];
            }
        } else if (stackNum == 2) {
            if (isEmpty(stackNum)) {
                System.out.println("栈为空");
                return -1;
            } else {
                return arr[near2];
            }
        } else {
            if (isEmpty(stackNum)) {
                System.out.println("栈为空");
                return -1;
            } else {
                return arr[near3];
            }
        }

    }

    public boolean isEmpty(int stackNum) {
        if (stackNum == 1) {
            return near1 == -1;
        } else if (stackNum == 2) {
            return near2 == -1 + arr.length;
        } else {
            return near3 == near2 + arr.length;
        }


    }
}

class TripleInOne {
    int arr[];
    int stackSize;
    int stackPushIndex[];//存放栈当前可以push的索引，

    public TripleInOne(int stackSize) {
        this.stackSize = stackSize;
        arr = new int[stackSize * 3];
        //数组中栈存储不是连续的
        stackPushIndex = new int[]{0, 1, 2};//就拿当前来看，第一个栈当前可push的索引是0,第二个栈当前可push的索引是1，第三个是2
    }

    //压栈操作
    public void push(int stackNum, int value) {//stackNum栈的下标，这个题是三个栈，对应关系是，0代表第一个栈，1代表第二个栈
        //先判断是否栈满
        //拿到当前栈可以push的索引，通过这个来判断当前栈是否满了
        int currentIndex = stackPushIndex[stackNum];//假设这里stackNum为0，表示获得第一个栈当前可以push的索引，即0

        if (currentIndex / 3 == stackSize) {
            System.out.println("栈满，无法继续压栈");
            return;
        }

        arr[currentIndex] = value;//压栈

        stackPushIndex[stackNum] += 3;//改变栈当前可以push的索引，

    }

    //弹栈
    public int pop(int stackNum) {
        //先判断是否栈空，
        if (isEmpty(stackNum)) {
            System.out.println("栈为空，无法弹栈");
            return -1;
        }

        int res = arr[stackPushIndex[stackNum] - 3];
        stackPushIndex[stackNum] -= 3;
        return res;

    }

    public int peek(int stackNum) {
        //先判断是否栈空
        if (isEmpty(stackNum)) {
            System.out.println("栈为空，无法peek");
            return -1;
        }

        return arr[stackPushIndex[stackNum] - 3];

    }


    public boolean isEmpty(int stackNum) {
        return stackPushIndex[stackNum] < 3;//栈当前可以push的索引，初始为0,1,2，如都没有改变，则不管你是哪个栈，都没有添加任何元素，即为空
    }

}

//面试题03.03 堆盘子
class StackOfPlates {


    int capacity;//盘子高度的阈值
    ArrayList<Stack<Integer>> list = new ArrayList<Stack<Integer>>();//用于存放栈


    public StackOfPlates(int cap) {
        this.capacity = cap;
    }


    public void push(int val) {
        if (capacity <= 0) {
            return;
        }

        //先判断集合中有无栈，若没有，新建一个栈来存放元素
        if (list.isEmpty()) {
            Stack newStack = new Stack<Integer>();
            newStack.add(val);
            list.add(newStack);

        } else {
            //集合中有栈，那么我们就使用这个栈来压栈，当然压栈前需判断是否满，若满，新建一个栈进行操作
            Stack stack = (Stack) list.get(list.size() - 1);
            if (stack.size() == capacity) {
                //老栈满了，新建栈进行操作
                Stack newStack = new Stack<Integer>();
                newStack.push(val);
                list.add(newStack);
                return;
            } else {
                //老栈没满，继续用老栈操作
                stack.push(val);
            }


        }

    }

    public int pop() {
        //先判断集合有无栈，若没有，则啥也返回不了
        if (list.size() == 0) {
            return -1;
        }

        //弹出老栈的栈顶元素
        Stack<Integer> stack = list.get(list.size() - 1);//拿到老栈
        int res = stack.get(stack.size() - 1);
        stack.remove(stack.size() - 1);//弹栈

        //判断这个老栈是否空了，若空了，就删除
        if (stack.isEmpty()) {
            list.remove(stack);
        }

        return res;

    }

    public int popAt(int index) {

        //先看看集合中有无栈，并且这个index是否合理
        if (list.size() == 0 || index > list.size() - 1) {
            return -1;
        }

        Stack<Integer> stack = list.get(index);//拿到指定下标的栈
        int res = stack.get(stack.size() - 1);
        stack.remove(stack.size() - 1);

        if (stack.size() == 0) {
            list.remove(stack);
        }


        return res;
    }

}

//面试题03.04 化栈为队
class MyQueue {

    Stack<Integer> stack;
    Stack<Integer> tempStack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stack = new Stack<>();//主栈，主栈永远只存放一个元素，即最后那个元素，这个元素最后出队（队列，先进先出
        tempStack = new Stack<>();//临时栈
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        //先判断主栈是否为空，若为空，直接放入主栈
        if (stack.isEmpty()) {
            stack.push(x);
            return;
        } else {
            //主栈不为空
            int num = stack.get(0);//拿到主栈底元素
            stack.clear();//清空主栈
            //判断临时栈是否为空
            if (tempStack.isEmpty()) {
                //直接放入临时栈
                tempStack.push(num);
                stack.push(x);

            } else {
                //临时栈不为空
                while (!tempStack.isEmpty()) {
                    stack.push(tempStack.pop());
                }
                tempStack.push(num);//将原来主栈栈底元素压入临时栈底
                while (!stack.isEmpty()) {
                    tempStack.push(stack.pop());
                }

                stack.push(x);
            }


        }


    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (tempStack.isEmpty()) {
            Integer pop = stack.pop();
            return pop;
        } else {
            Integer pop = tempStack.pop();
            return pop;
        }

    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (tempStack.isEmpty()) {
            return stack.peek();
        } else {
            return tempStack.peek();
        }

    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return tempStack.isEmpty() && stack.isEmpty();
    }
}

//面试题03.05 栈排序
class SortedStack {

    Stack<Integer> stack;//主栈
    Stack<Integer> tempStack;//临时栈


    public SortedStack() {
        stack = new Stack<>();
        tempStack = new Stack<>();
    }

    public void push(int val) {
        //判断主栈是否为空，若为空，直接将val压栈
        if (stack.isEmpty()) {

            stack.push(val);
            return;
        } else {
            //主栈不为空，则将val和主栈栈顶元素进行比较，
            if (val <= stack.get(stack.size() - 1)) {
                //若val小于主栈栈顶元素，直接放入
                stack.push(val);
                return;
            } else {
                //若val大于等于主栈栈顶元素，就要进行排序了
                tempStack.push(stack.pop());
                while (!stack.isEmpty() && val > stack.get(stack.size() - 1)) {
                    tempStack.push(stack.pop());
                }
                //将val压入主栈
                stack.push(val);
                while (!tempStack.isEmpty()) {//将临时栈的元素弹出并且压入主栈
                    stack.push(tempStack.pop());
                }

            }

        }

    }

    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        stack.remove(stack.get(stack.size() - 1));

    }

    public int peek() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.get(stack.size() - 1);
    }

    public boolean isEmpty() {
        return stack.size() == 0;
    }
}


class Son extends Father {

    static int num = 18;
    int x = 15999;

    static {
        System.out.println("子类静态块");
    }


    public Son() {
        System.out.println("子无参构造");
    }

    {
        System.out.println("子类代码块");

    }

    public Son(int x) {
        System.out.println("构造方法执行了啊，都篮子" + x);

    }
}

class Father {
    static int num = 15;
    int x = 999;

    static {

        System.out.println("父类静态块");
    }


    public Father() {
        System.out.println("父类无参构造");
    }

    {
        System.out.println("父类代码块");

    }

}